package baseclass.d_list;


import utils.ListNode;

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;

/**
 * @date 2020/2/28 22:14
 */
public class Code09_MergeKSortedList {
    /**
     *  方式1：把所有节点value放入数组，然后对数组排序吗，重构
     *  或者把所有节点放入小跟堆。
     *  时间O(NlogN),空间O(N)。N为总结点个数
     */
    public static ListNode mergeKLists1(ListNode[] lists) {
        if (lists == null || lists.length <= 0)  return null;
        List<Integer> list = new LinkedList<>();
        //把所有节点放在数组中。
        for (ListNode listNode : lists) {
            while (listNode != null) {
                list.add(listNode.val);
                listNode = listNode.next;
            }
        }
        //有可能是[[],[]]
        if (list.size() == 0) {
            return null;
        }
        //把数组排序
        Collections.sort(list);
        //重构链表
        ListNode head = new ListNode(list.get(0));
        ListNode cur = head;
        for (int i = 1; i < list.size(); i++) {
            cur.next = new ListNode(list.get(i));
            cur = cur.next;
        }
        return head;
    }
    /**
     * 方式2：把每个链表的头放入小跟堆。然后从小跟堆放入拿最小，
     * 所属链表再把next放入小跟堆。
     * 时间O(NlogK),空间O(K)
     */
    public static ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length <= 0) return null;
        PriorityQueue<ListNode> minQueue = new PriorityQueue<>((l1, l2) -> l1.val - l2.val);
        for (int i = 0; i < lists.length; i++) {
            //list[i]是第i个链表的头结点
            if (lists[i] != null) {
                minQueue.add(lists[i]);
            }
        }
        ListNode head = new ListNode(-1);
        ListNode cur = head;
        while (!minQueue.isEmpty()) {
            //弹出value最小的ListNode的节点
            ListNode tempNode = minQueue.poll();
            //连接到当前的cur
            cur.next = tempNode;
            cur = cur.next;
            //把所属的链表的下一个节点加入queue
            if (tempNode.next != null) {
                minQueue.add(tempNode.next);
            }
        }
        return head.next;
    }
    /**
     * 方式3：归并排序。归并的最后是两个链表，给两个链表排序
     * 时间:O(Nlogk)，空间看递归栈。
     */
    public static ListNode mergeKLists3(ListNode[] lists) {
        if (lists == null || lists.length <= 0) {
            return null;
        }
        return merge(lists, 0, lists.length - 1);
    }

    private static ListNode merge(ListNode[] lists, int left, int right) {
        if (left >= right) {
            return lists[left];
        }
        int mid = left + (right - left) / 2;
        ListNode l1 = merge(lists, left, mid);
        ListNode l2 = merge(lists, mid + 1, right);
        return mergeTwoList(l1, l2);
    }

    /**
     * 归并两个有序链表，三种方法，见{@link Code09_MergeTwoSortedList}
     *
     */
    private static ListNode mergeTwoList(ListNode l1, ListNode l2) {
        if (l1 == null || l2 == null) {
            return l1 == null ? l2 : l1;
        }
        ListNode node;
        if (l1.val < l2.val) {
            node = l1;
            node.next = mergeTwoList(l1.next, l2);
        } else {
            node = l2;
            node.next = mergeTwoList(l1, l2.next);
        }
        return node;
    }





}
